package LeetCode.month02.day36;

public class No42 {
    public int trap(int[] height) {
//        int n = height.length;
//        int res = 0;
////        int[] preMax = new int[n];
//        int[] left = new int[n];
//        int[] right= new int[n];
//        left[0]=height[0];
//        right[n-1]=height[n-1];
//        for (int i = 1; i < n; i++) {
//            left[i]=Math.max(height[i],left[i-1]);
//            right[n-i-1] = Math.max(height[n-i-1],right[n-i]);
//        }
//        for (int i = 0; i < n; i++) {
//            res+=Math.min(left[i],right[i])-height[i];
//        }
//        return res;

        int n = height.length;
        int res = 0;
        int leftmax = 0;
        int rightmax= 0;
        int left =0;
        int right = n-1;
        while(left<=right){
            leftmax = Math.max(leftmax,height[left]);
            rightmax = Math.max(rightmax,height[right]);
            if(leftmax<rightmax){
                res+=leftmax-height[left++];
            }else{
                res+=rightmax-height[right--];
            }
        }
        return res;
    }
}
